743B - Chloe and the sequence - CodeForces Solution


binary search bitmasks constructive algorithms implementation *1200

Please click on ads to support us..

Python Code:

import math

a, k = map(int, input().split())

if k % 2 != 0:
    print(1)
    exit()

if k & k-1 == 0:
    print(int(math.log2(k)) + 1)
    exit()

l = 2 ** math.floor(math.log2(k)) + 1
r = 2 ** math.ceil(math.log2(k)) - 1
center = (l + r) // 2

n = math.floor(math.log2(k))

while center != k:
    if center > k:
        r = center - 1
    else:
        l = center + 1
    
    center = (l + r) // 2
    n -= 1
    
print(n)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long int
#define ull unsigned long long int
#define nl "\n"
#define MOD 1e9+7
#define pb push_back
#define ppb pop_back
#define dbg(x) cerr<<#x<<"-"<<x<<nl;

/* solve function */
void solve(){
    ll n,k;
    cin>>n>>k;
    ll x = 2;
    int i=1;
    while(x<=pow(2,n)){
        if(k%x == x/2){
            cout<<i<<nl;
            return;
        }
        ++i;
        x *= 2;
    }
    cout<<-1<<nl;
}


/* main function */
int main(){
    clock_t start,end;
    start=clock();
    fast();
    ll t=1;
    ll i=1;
    /* cin>>t; */
    while(t--){
        /* cout<<"Case# "<<i<<": "; */
        solve();
        i++;
    }
    end=clock();
    double time=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<nl<<"Time: "<<time<<" sec"<<nl;
}


Comments

Submit
0 Comments
More Questions

1656B - Subtract Operation
1656A - Good Pairs
1367A - Short Substrings
87A - Trains
664A - Complicated GCD
1635D - Infinite Set
1462A - Favorite Sequence
1445B - Elimination
1656C - Make Equal With Mod
567A - Lineland Mail
1553A - Digits Sum
1359B - New Theatre Square
766A - Mahmoud and Longest Uncommon Subsequence
701B - Cells Not Under Attack
702A - Maximum Increase
1656D - K-good
1426A - Floor Number
876A - Trip For Meal
1326B - Maximums
1635C - Differential Sorting
961A - Tetris
1635B - Avoid Local Maximums
20A - BerOS file system
1637A - Sorting Parts
509A - Maximum in Table
1647C - Madoka and Childish Pranks
689B - Mike and Shortcuts
379B - New Year Present
1498A - GCD Sum
1277C - As Simple as One and Two